#include "brelaz.h"

void brelaz(Grafo *grafo){

    // Clique más grande usando dsatur.
    vector<int> order;
    dsatur(grafo, &order);

    // desplazar las ids para que comienzen en 1
    order.insert(order.begin(), 0);

    // Es la serie más larga de crecimiento monotono en colores de los 
    // nodos según la salida de dsatur y el orden en el que procesó los nodos.
    int lbegin = 1, bbegin = 1, bend = -1;
    for (int i = 2; i < order.size(); ++ i) {
        if (grafo->getNodo(order[i])->getColor() - 1 != grafo->getNodo(order[i - 1])->getColor()) {
            if (bend - bbegin < i - lbegin) {
                bend = i;
                bbegin = lbegin;
            }
            lbegin = i;
        }
    }
    if (-1 == bend) {
        bend = order.size();
    }
    bbegin = 1;
    bend = 2;

    int t = 1, *brelazInv = new int[order.size() + 1],
               *coloring = new int[order.size() + 1];
    bool *label = new bool[order.size() + 1];
    Nodo **brelazOrd = new Nodo*[order.size() + 1];
    // Inicializar los colores de la clique y colocarlos al principio
    for (int i = bbegin; i < bend; ++ i) {
        brelazOrd[t] = grafo->getNodo(order[i]);
        coloring[t] = i - bbegin + 1;
        brelazInv[brelazOrd[t]->getId()] = t;
        label[t] = true;
        ++ t;
    }

    int q = 0;
    // Incluir los demás
    for (int i = 1; i < order.size(); ++ i) {
        if (i < bbegin || bend <= i) {
            brelazOrd[t] = grafo->getNodo(order[i]);
            coloring[t] = 0;
            brelazInv[brelazOrd[t]->getId()] = t;
            label[t] = false;
            ++ t;
        }
        int m = grafo->getNodo(order[i])->getColor();
        q = q < m ? m : q;
    }

    bool back = false;
    int w = bend - bbegin, k = w + 1, *minColored = new int[q + 1];
    vector<int>* U = new vector<int>[order.size() + 1];
    int mo = 0;
    while (true) {
        coloring[k] = 0;
        if (back) {
            U[k].erase(U[k].begin());
            label[k] = false;
        } else {
            // obtener colores usados
            int uk = 0;
            for (int i = 1; i < k; ++ i) {
                uk = uk < coloring[i] ? coloring[i] : uk;
            }
            // generar la lista de colores viables
            U[k].clear();
            vector<Nodo*> ady = brelazOrd[k]->getAdyacentes();
            for (int i = 1; i <= (uk + 1 < q - 1 ? uk + 1 : q - 1); ++ i) {
                bool usable = true;
                for (int j = 0; j < ady.size(); ++ j) {
                    // en caso de ser adyacente consigo mismo, ningún color es descartado ya que el suyo es cero
                    if (coloring[brelazInv[ady[j]->getId()]] == i) {
                        usable = false;
                        break;
                    }
                }
                if (usable) {
                    U[k].push_back(i);
                }
            }
        }

        if (0 < U[k].size()) {
            coloring[k] = U[k][0];
            ++ k;
            if (k == order.size()) {
                q = 0;
                // registrar la nueva mejor coloración
                for (int i = 1; i < order.size(); ++ i) {
                    brelazOrd[i]->setColor(coloring[i]);
                    q = q < coloring[i] ? coloring[i] : q;
                }
                // en caso de haber alcanzado la clique es porque inicialmente nos dieron la clique máxima
                if (q == w) {
                    break;
                }
                // encontrar el nodo al cual vamos a hacer backtrack, el que tiene color más alto y rank más bajo
                for (int i = 1; i < order.size(); ++ i) {
                    if (coloring[i] == q) {
                        k = i;
                        break;
                    }
                }
                for (int i = k; i < order.size(); ++ i) {
                    label[i] = false;
                }
                back = true;
            } else {
                back = false;
            }
        } else {
            back = true;
        }
        if (back) {
            // inicializar colores
            for (int i = 0; i <= q; ++ i) {
                minColored[i] = 0;
            }
            // encontrar el primer nodo de los adyacentes para cada color
            vector<Nodo*> ady = brelazOrd[k]->getAdyacentes();
            for (int i = 0; i < ady.size(); ++ i) {
                int o = brelazInv[ady[i]->getId()];
                if (o < minColored[coloring[o]] || minColored[coloring[o]] == 0) {
                    minColored[coloring[o]] = o;
                }
            }
            // etiquetar nodos característicos:
            // 1. aparecen antes de el nodo k en brelazOrd
            // 2. son adyacentes al nodo k
            // 3. son los primeros en su color dentro de los adyacentes al nodo k
            for (int i = 0; i < ady.size(); ++ i) {
                int o = brelazInv[ady[i]->getId()];
                if (o < k && o == minColored[coloring[o]]) {
                    label[o] = true;
                }
            }

            // encontrar máximo nodo etiquetado antes de k
            for (int i = k - 1; i > 0; -- i) {
                if (label[i]) {
                    k = i;
                    break;
                }
            }

            // el máximo nodo etiquetable está en la clique inicial
            if (k <= w) {
                break;
            }
        }
    }

    grafo->imprimir();

    delete[] brelazOrd;
    delete[] brelazInv;
    delete[] minColored;
    delete[] coloring;
};